package greedy

import (
	"math"
	"strings"
)

func GetMinLight (road string) int {
	if len(road) == 0 {return 0 }
	return GetMinLightProcess(strings.Split(road, ""), 0, map[int]struct{}{})
}

func GetMinLightProcess(roadStrs []string, start int, lightSet map[int]struct{}) int {
	if start == len(roadStrs) {
		for i:=0; i<len(roadStrs); i++ {
			if roadStrs[i] != "X" {
				if !IsCover(i, lightSet) {
					return math.MaxInt64
				}
			}
		}
		return len(lightSet)
	}
	no := GetMinLightProcess(roadStrs, start+1, lightSet)
	yes := math.MaxInt64
	if roadStrs[start] != "X" {
		lightSet[start] = struct{}{}
		yes = GetMinLightProcess(roadStrs, start+1, lightSet)
		delete(lightSet, start)
	}
	return min(yes, no)
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func IsCover(index int, lightSet map[int]struct{}) bool {
	_, ok1 := lightSet[index-1]
	_, ok2 := lightSet[index]
	_, ok3 := lightSet[index+1]
	return ok1 || ok2 || ok3
}

func GetMinLight1(road string) int {
	if len(road) == 0 {return 0 }
	var light int
	var index int
	for index < len(road) {
		if road[index] == 'X' {
			index++
		} else {
			light++
			if index+1 == len(road) {
				break
			} else {
				if road[index+1] == 'X' {
					index = index + 2
				} else {
					index = index + 3
				}
			}
		}
	}
	return light
}
